package dp

// https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484
// 算法: 贪心
// 一直累加即可，如果当前加的负数已经低于0，则停止添加
// 时间复杂度: O(n)
func maxInt(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func FindGreatestSumOfSubArray(array []int) int {
	if len(array) == 0 {
		return 0
	}

	currentSum, maxSum := 0, 0

	for index := 0; index < len(array); index++ {
		if currentSum+array[index] > 0 {
			currentSum += array[index]
		} else {
			currentSum = 0
		}
		maxSum = maxInt(maxSum, currentSum)
	}

	// 特殊情况: 如果数组中的数全是负数，需要找到最大的那个负数
	if 0 == maxSum {
		maxSum = array[0]
		for index := 1; index < len(array); index++ {
			maxSum = maxInt(maxSum, array[index])
		}
	}
	return maxSum
}
